package com.aqie.easy.math;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 942. 增减字符串匹配
 */
public class DiStringMatch {

    /**
     * 双指针
     * 如果是I 则 递增, D 则递减
     * 设numi=0,numd=S.length()，遇到D就把numd--推后，遇到I就把numi++推后。
     * @param S
     * @return
     */
    public int[] diStringMatch(String S) {
        int length = S.length();
        int numi = 0, numd = length;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i<length; i++){
            if (S.charAt(i) == 'I'){
                list.add(numi++);
            }else{
                list.add(numd--);
            }
        }
        list.add(numd);
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }

    /**
     1. 方法：
     a. 每次根据I或D选取A中最小或最大的数字，已经用过的去掉，从没用过的里面选。
     2. 原理：
     a. 如I D I D，输出 0 4 1 3 2
     b. 为I，则选取没用过的最小的数字，0；这样，之后的每个数字，无论怎么选，都是 < 0的，
     也就是说，无论后面的数字是什么，都满足  S[i] == "I"，那么 A[i] < A[i+1]  这个条件
     c. 为D，同理。
     */
    public int[] diStringMatch3(String S) {

        char[] cs = S.toCharArray();
        int min = 0, max = cs.length;
        int[] a = new int[max+1];

        for (int i = 0; i < cs.length; i++) {
            if (cs[i] == 'I'){
                a[i] = min;
                min++;
            }else {
                a[i] = max;
                max--;
            }
        }
        a[cs.length] = max;

        return a;
    }

    public static void main(String[] args) {
        // 用stream int[] 转 List用stream int[] 转 List
        int[] array = {1,2,3,4,5,6,7,8,9,10};
        List<Integer> list = Arrays.stream(array).boxed().collect(Collectors.toList());
    }
}
